
using System;

using System.Collections.Generic;
using UnityEngine;

public class Solution : MonoBehaviour
{

    public class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int x) { val = x; }
    }
    void Start()
    {
        int[] nums = { 5, 5, 6, 6, 7, 8, 1, 2, 3, 4, 5 };
        //Debug.Log(MinArray(nums));
        nums = GetLeastNumbers(nums, 1);
        for (int i = 0; i < nums.Length; i++)
        {
            Debug.Log(nums[i]);
        }
    }



    //快速排序模板：
    //快速排序基本思想：选取一个比较值 ，然后从左右两个节点开始进行比较，大于此值的放入比较节点右边，小于的同理，然后分别对两边进行递归操作
    //复杂度O（nlog2n）,极限情况下是n^2
    // void quick_sort(int q[] , int l , int r)
    // {
    //     if(l >= r) return; //表示此区间只有一个数或者没有数

    //     int i = l - 0 , j = r + 1 , x = q[l + r >> 1]; //i为左指针，j为右指针 x为每一次分割区间时选定的比较数  >> 这个是右移运算符，是位运算的一种，将一个整数右移一位表示除以2 
    //     while(i < j)
    //     {
    //         do ++ i; while(q[i] < x); //左指针寻找小于x的数
    //         do -- j; while(q[j] > x); //右指针寻找大于x的数
    //         if(i < j) swap(q[i] < q[j]); //swap函数存在于C++的algorithm头文件中，相当于自己手写的交换变量函数，因为指针停下来的时候可能是穿过，重合这两种情况其中一种，如果未相遇我们就交换指针所指的数，然后直到l>=r循环结束
    //     }
    //     //每一次递归之后i、j的相对位置只有两种情况，i==j或者i==j+1
    //     quick_sort(q , l , j) , quick_sort(q , j + 1 , r);//递归处理左右区间，先左，再右（注意划分区间用的是i还是j）
    // }


    public int[] GetLeastNumbers(int[] arr, int k)
    {
        //先排序
        quick_sort2(arr, 0, arr.Length - 1);
        return arr;
    }

    void quick_sort(int[] q, int l, int r)
    {
        if (l >= r) return;

        int a = (l + r) >> 1;
        int x = q[a];
        int i = l - 1;
        int j = r + 1;
        while (i < j)
        {
            do ++i; while (q[i] < x);
            do --j; while (q[j] > x);
            if (i < j)
            {
                int temp = 0;
                temp = q[i];
                q[i] = q[j];
                q[j] = temp;
            }// swap(q[i] , q[j]);
        }
        quick_sort(q, l, j);
        quick_sort(q, j + 1, r);
    }



    public void quick_sort2(int[] arr, int l, int r)
    {

        if (l >= r)
        {
            return;
        }
        int x = arr[(l + r) >> 1];
        int i = l-1;
        int j = r+1;
        int count = 0;
        while (i < j)
        {
            if (count >= 10000)
            {
                Debug.LogError("超循环了");
                break;
            }
            count++;
     
            while (arr[i] < x)
            {
                i++;
            }
            while (arr[j] > x)
            {
                j--;
            }
            if (i < j)
            {
                int temp = 0;
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
                j++;
            }
        }
        quick_sort2(arr, l, j);
        quick_sort2(arr, j + 1, r);
    }

}